//四数之和
#include<iostream>
#include<vector>
using namespace std;

class Solution
{
public:
 vector<vector<int> > fourSum(vector<int>& nums, int target) 
 {
 vector<vector<int> > ret;
 // 1. 排序
 sort(nums.begin(), nums.end());
 // 2. 利⽤双指针解决问题
 int n = nums.size();
 for(int i = 0; i < n; ) // 固定数 a
 {
 // 利⽤ 三数之和
 for(int j = i + 1; j < n; ) // 固定数 b
 {
 // 双指针
 int left = j + 1, right = n - 1;
 long long aim = (long long)target - nums[i] - nums[j];
 while(left < right)
 {
 int sum = nums[left] + nums[right];
 if(sum < aim) left++;
 else if(sum > aim) right--;
 else
 {
 ret.push_back({nums[i], nums[j], nums[left++], nums[right--]});
 // 去重⼀
 while(left < right && nums[left] == nums[left - 1]) 
left++;
 while(left < right && nums[right] == nums[right + 1]) 
right--;
 }
 }
 // 去重⼆
 j++;
 while(j < n && nums[j] == nums[j - 1]) j++;
 }
 // 去重三
 i++;
 while(i < n && nums[i] == nums[i - 1]) i++;
 }
 return ret;
 }
};